public class MinWindow {
    // leetcode 最小覆盖字串
    // https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked
    public String minWindow(String s, String t) {
        // 需要记录t字符串的种类和数量
        int type1 = 0;
        int[] hash1 = new int[58];
        char[] ss = s.toCharArray(), tt = t.toCharArray();
        int minLength = 100001, minLeft = -1, minRight = -1;
        for (char c : tt) {
            hash1[c-'A']++;
            if (hash1[c-'A'] == 1) type1++;
        }
        int left = 0, right = 0, count = 0, len = ss.length, type2 = 0;
        int[] hash2 = new int[58];
        while (right < len) {
            char in = ss[right];
            hash2[in - 'A']++;
            if (hash1[in - 'A'] > 0) {
                if (hash2[in - 'A'] == hash1[in - 'A']) type2++;
                count++;
            }
            right++;
            while (type2 == type1) {
                // 更新结果
                if (type1 == type2 && count >= tt.length) {
                    if (right - left < minLength) {
                        minLength = right - left;
                        minLeft = left;
                        minRight = right;
                    }
                }
                char out = ss[left];
                hash2[out - 'A']--;
                if (hash1[out - 'A'] > 0) {
                    count--;
                    if (hash2[out - 'A'] < hash1[out - 'A']) type2--;
                }
                left++;
            }
        }
        return minLength == 100001 ? "" : s.substring(minLeft,minRight);
    }
}
